package a08_回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <p>
 * a05_电话号码的字母组合复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/2/10
 */
public class a05_电话号码的字母组合复习2 {

    public static void main(String[] args) {
        List<String> list = letterCombinations("23");
        System.out.println();
    }

    public static List<String> letterCombinations(String digits) {

        List<String> result = new ArrayList<>();
        if (digits.equals("")) {
            return result;
        }
        String[] phoneArray = new String[]{
                "",
                "",
                "abc",
                "def",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz"
        };
        char[] digitsCharArray = digits.toCharArray();
        int[] digitsArray = new int[digitsCharArray.length];
        for (int i = 0; i < digitsArray.length; i++) {
            digitsArray[i] = Integer.valueOf(digitsCharArray[i] + "");
        }


        LinkedList<Character> path = new LinkedList<>();
        traversal(result, path, phoneArray, digitsArray, 0);
        return result;

    }

    private static void traversal(List<String> result,
                           LinkedList<Character> path,
                           String[] phoneArray,
                           int[] digitsArray,
                           int startIdx){
        if(startIdx == digitsArray.length){
            String collect = path.stream().map(c -> c.toString()).collect(Collectors.joining());
            result.add(collect);
            return;
        }

        char[] chars = phoneArray[digitsArray[startIdx]].toCharArray();
        for (int i = 0; i < chars.length; i++) {
            path.add(chars[i]);
            traversal(result, path, phoneArray, digitsArray, startIdx + 1);
            path.removeLast();
        }
    }
}
